package Algorithm.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/1/14
 * @author—Email liujunfirst@outlook.com
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 组合数
 * 给定数组 array=[1,3,6,8,5] 和 给定的目标值 target=9
 * 数组可以无限重复的选择，最终给出符合target的序列
 * 比如符合给定数组和目标值的序列为：
 * [[1,1,1,6],
 * [1,8],
 * [3,6],
 * [1,3,5],
 * [1,1,1,1,5]]
 */
public class CombinationNum {

    List list_all;
    List list_temp;
    int target;
    int sum;
    int[] array;

    public List<List<Integer>> getTergetList(int[] array, int target) {
        if (array == null || array.length == 0) {
            return null;
        }
        list_all = new ArrayList();
        list_temp = new ArrayList();
        //为防止出现重复，比如：[1,1,1,3]、[1,1,3,1]、[3,1,1,1]，需要控制去重复
        Arrays.sort(array);
        this.array = array;
        this.target = target;
        this.sum = 0;
        count(0);
        sort();
        return list_all;
    }

    private void count(int depth) {
        if (sum == target) {
            list_all.add(new ArrayList<>(list_temp));
            return;
        }
        if (sum > target) {
            return;
        }
        //为了防止重复，允许重复选取自身，但是不可以选择前面的元素
        for (int i = depth; i < this.array.length; i++) {
            sum += array[i];
            list_temp.add(array[i]);
            count(i);
            list_temp.remove(list_temp.size() - 1);
            sum -= array[i];
        }
    }

    private void sort() {

    }
}
